package array;

public class leetCode329_longestIncreasingPath {
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,1,-1};
    int[][] matrix;
    int[][] result; // result 记录的是长度
    int max = 0;
    int n;
    int m;

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0)return 0;
        this.matrix = matrix;
        this.n = matrix.length;
        this.m = matrix[0].length;
        result = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                max = Math.max(max,build(i,j));
            }
        }
        return max;
    }

    public int build(int x,int y){
        if(result[x][y] != 0) return result[x][y];
        result[x][y]++;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(matrix[nx][ny] > matrix[x][y]){
                result[x][y] = Math.max(result[x][y],build(nx,ny)+1);
            }

        }
        return result[x][y];
    }

    public static void main(String[] args) {
        int[][] nums = {{9,9,4},{6,6,8},{2,1,1}};
        leetCode329_longestIncreasingPath f = new leetCode329_longestIncreasingPath();
        f.longestIncreasingPath(nums);
    }
}
